/**
 * 有效的数独
 *
 * 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 *
 * 注意：
 * 一个有效的数独（部分已被填充）不一定是可解的。
 * 只需要根据以上规则，验证已经填入的数字是否有效即可。
 * 空白格用 '.' 表示。
 *
 * 示例 1：
 * 输入：board =
 * [["5","3",".",".","7",".",".",".","."]
 * ,["6",".",".","1","9","5",".",".","."]
 * ,[".","9","8",".",".",".",".","6","."]
 * ,["8",".",".",".","6",".",".",".","3"]
 * ,["4",".",".","8",".","3",".",".","1"]
 * ,["7",".",".",".","2",".",".",".","6"]
 * ,[".","6",".",".",".",".","2","8","."]
 * ,[".",".",".","4","1","9",".",".","5"]
 * ,[".",".",".",".","8",".",".","7","9"]]
 * 输出：true
 *
 * 示例 2：
 * 输入：board =
 * [["8","3",".",".","7",".",".",".","."]
 * ,["6",".",".","1","9","5",".",".","."]
 * ,[".","9","8",".",".",".",".","6","."]
 * ,["8",".",".",".","6",".",".",".","3"]
 * ,["4",".",".","8",".","3",".",".","1"]
 * ,["7",".",".",".","2",".",".",".","6"]
 * ,[".","6",".",".",".",".","2","8","."]
 * ,[".",".",".","4","1","9",".",".","5"]
 * ,[".",".",".",".","8",".",".","7","9"]]
 * 输出：false
 * 解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
 * 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
 *
 * 提示：
 * board.length == 9
 * board[i].length == 9
 * board[i][j] 是一位数字（1-9）或者 '.'
 */

/**
 * 我们用暴搜将所有行和列的元素分别放在数组里, 判断数组中的个数是否会大于 2, 要是大于 2, 就说明
 * 不是有效数独
 * 时间复杂度 : O(1)
 * 空间复杂度 : O(1)
 */

public class Main {

    // 将数组长度定义为 static, 这里可以随意改变数组长度
    static int n = 9;
    // 这个为每行列分的组数
    static int m = 3;
    public boolean isValidSudoku(char[][] board) {

        // 第一个 n 是行列的行数, 后面一个 n 是因为一共有 n 个数
        // 这两个肯定会是一样的, 解释下防止会把含义弄混
        int[][] col = new int[n][n];
        int[][] row = new int[n][n];

        // 这里的第一个三表示的是行被分为的三个,
        // 第二个三是表示的列被分为的三个
        // 后面的 n 表示的是 有 n 个数字
        int[][][] space = new int[m][m][n];

        // 两次循环将所有的数都遍历到
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {

                // 要是 . 就跳过
                if (board[i][j] == '.') {
                    continue;
                }

                // 这里要多减一, 保持与数组下标对应
                int in = board[i][j] - '0' - 1;

                // 行数组
                col[i][in]++;

                // 列数组
                row[in][j]++;

                // 这里提前将下标映射好, 一个矩阵中的元素放在一个数组中
                int a = i / m;
                int b = j / m;
                space[a][b][in]++;

                // 这里判断下 行 列 矩阵中的元素是否重复出现
                if (col[i][in] > 1 || row[in][j] > 1 || space[a][b][in] > 1) {

                    // 要是重复出现就返回 false
                    return false;
                }
            }
        }

        // 循环结束后还没有问题就返回 true
        return true;
    }
}